{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*注释：侯捷书籍聚焦 SGI STL（C++98 前），理解旧实现后再吸收 C++11–23 的新语义，可明显降低现代标准库学习门槛。*\n",
    "\n",
    "- **学习节奏建议**\n",
    "  1. 阅读书中绪论，掌握 SGI 六大构件及配置方式。\n",
    "  2. 先啃基础设施（allocator、iterator、traits），再进入容器、算法与适配器。\n",
    "  3. 每读完一章，即对照 C++11–23 的对应演进特性，更新思维框架。\n",
    "- **时间线概览（语言/库核心里程碑）**\n",
    "  - **C++11**：移动语义、左/右值引用、`auto`、`nullptr`、lambda、`std::thread`、`std::unordered_*`、`std::shared_ptr`、`std::array`、`std::forward_list`。\n",
    "  - **C++14**：泛型 lambda、返回类型推断、`std::make_unique`、`std::shared_timed_mutex`。\n",
    "  - **C++17**：结构化绑定、`if constexpr`、`std::optional/variant/any`、`std::string_view`、并行 STL 算法、`node_handle`、`try_emplace`。\n",
    "  - **C++20**：concepts、ranges（views/algorithms）、`constexpr` 容器/算法、`std::span`、`std::bit_cast`、`std::erase` 系列函数、协程 TS、`std::atomic_ref`。\n",
    "  - **C++23**：`std::expected`、`std::mdspan`、`std::print`、`std::ranges::to`、`std::move_only_function`、`std::flat_map`、`std::adjacent`, `std::chunk`, `std::slide` 等范围视图、更多 `constexpr`/`noexcept` 加强。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基础设施篇（Allocator / Iterator / Traits / 未初始化工具）\n",
    "\n",
    "\n",
    "Allocator / 内存管理\n",
    "- **SGI 回顾**：双层配置器（`__malloc_alloc_template` + `__default_alloc_template`）构建对象池。\n",
    "- **C++11–17 补充**\n",
    "  - 引入 **move 构造/赋值**，容器需在 reallocate 时优先调用移动操作。\n",
    "  - `std::allocator_traits`（C++11）统一 allocator 接口，支持 `propagate_on_container_*`.\n",
    "  - `shrink_to_fit`, `max_size` 规范化；`std::unique_ptr`、`std::shared_ptr` 改变资源管理习惯。\n",
    "- **C++20–23 补充**\n",
    "  - `std::pmr` 多态内存资源体系（C++17 进入 TS，C++17 正式），理念与 SGI 二级配置器相通，但接口现代化。\n",
    "  - `constexpr` allocator 支持，容器在常量表达式中可构造/销毁。\n",
    "  - `std::start_lifetime_as`, `std::launder`, `std::construct_at`、`std::destroy_at` 完善对象生存期语义。\n",
    "\n",
    "Iterator / Traits / Concepts\n",
    "- **SGI 回顾**：迭代器类别标签 + `iterator_traits`。\n",
    "- **C++11–17**\n",
    "  - move 迭代器 `std::move_iterator`（C++11）、`std::reverse_iterator` constexpr 化。\n",
    "  - `std::next`, `std::prev`、`std::begin`, `std::end` 成为标准接口。\n",
    "- **C++20–23**\n",
    "  - **Concepts** 定义 `std::input_iterator`, `std::random_access_iterator`, `std::contiguous_iterator`。\n",
    "  - Ranges 框架提供 `std::ranges::iterator_t`, `std::ranges::sentinel_t`, `std::ranges::advance/distance`。\n",
    "  - `ranges::subrange`, `views::all`, `views::counted` 提供更现代的迭代区间表达能力。\n",
    "\n",
    "构造/销毁与未初始化算法\n",
    "\n",
    "- **SGI 回顾**：`construct`, `destroy`, `uninitialized_copy/fill`。\n",
    "- **C++11–17**\n",
    "  - 引入 `std::uninitialized_move`, `std::uninitialized_move_n` 支持移动语义。\n",
    "  - `std::allocator_traits::construct/destroy` 正式成为使用入口。\n",
    "- **C++20–23**\n",
    "  - 几乎全部未初始化算法均可 `constexpr`。\n",
    "  - `std::destroy`/`std::destroy_n` 支持 ranges；`std::ranges::uninitialized_*` 版本提供 sentinel 友好接口。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 序列容器篇（Sequence Containers）\n",
    "\n",
    "`vector`\n",
    "- **SGI**：倍增扩容、`insert/erase` 元素搬移、内存池使用。\n",
    "- **C++11–17**\n",
    "  - move/emplace 系列（`emplace_back`, `emplace`）显著降低复制成本。\n",
    "  - `data()` 返回指针（C++11），`shrink_to_fit`（C++11）。\n",
    "  - `std::vector<bool>` 的位压缩依旧存在争议，但 C++17 引入透明访问器。\n",
    "- **C++20–23**\n",
    "  - `constexpr` 构造、赋值、`push_back`、`emplace_back`。\n",
    "  - 与 ranges 结合：`std::ranges::sort`, `std::ranges::to<std::vector>`。\n",
    "  - C++23：`std::vector` 提供 `resize_and_overwrite`，与 SGI 自定义 `resize` 对比。\n",
    "\n",
    "`list` / `forward_list`\n",
    "- **SGI**：链表节点复用、`splice` 常数时间。\n",
    "- **C++11–17**\n",
    "  - `std::forward_list` 进入标准（C++11），对应 SGI `slist`。\n",
    "  - `splice`, `merge`, `sort` 支持移动语义；`remove`, `unique` 新增同阶段 `erase` 自由函数（C++20）。\n",
    "- **C++20–23**\n",
    "  - `list`, `forward_list` 几乎全 `constexpr`。\n",
    "  - `std::ranges::sort` 不支持非随机访问容器，但 `std::ranges::list` 支持 `ranges::sort` 特化。\n",
    "\n",
    "`deque`\n",
    "- **SGI**：中控器（map）+ 缓冲区的段式存储。\n",
    "- **C++11–23**\n",
    "  - 迭代器支持 `constexpr`；`shrink_to_fit`（C++11）尽量释放冗余块。\n",
    "  - `std::ranges::is_nothrow_swappable` 等概念要求 `deque` 提供 `noexcept` swap。\n",
    "\n",
    "> 在侯捷《STL 源码剖析》中谈到 `deque` 的实现时，“中控器（map）”指的不是 C++ 里的 `std::map`，而是 **用于管理多个缓冲区（buffer）的“中心控制结构”**。英文原文里通常称它为 **map** 或 **control map**，直译容易误解成关联容器，所以书中把它称作“中控器”\n",
    "\n",
    "`stack` / `queue` / `priority_queue`\n",
    "\n",
    "- **C++11–17**：支持移动构造/赋值；`emplace`。\n",
    "- **C++20–23**：`constexpr`；`priority_queue` 可接受 `std::span` 构造；未来提案 `P1467` 讨论 `push_heap` `constexpr` 化。\n",
    "\n",
    "新增序列容器\n",
    "\n",
    "- **C++11**：`std::array`、`std::forward_list`。\n",
    "- **C++17**：`std::string_view`（轻量视图）。\n",
    "- **C++20**：`std::span`、`std::mdspan`（TS，C++23 正式）提供多维视图，理念类似 SGI `deque` 的分段访问。\n",
    "- **C++23**：`std::flat_map` / `std::flat_set` 官方化（排序向量 + 二分查找），可视作“vector + lower_bound”的标准化体现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联容器篇（Associative Containers）\n",
    "\n",
    "`rb_tree` 与传统关联容器\n",
    "\n",
    "- **SGI**：红黑树节点、旋转、插入/删除。\n",
    "- **C++11–17**\n",
    "  - `emplace`, `try_emplace`, `insert_or_assign` 提升构造效率。\n",
    "  - `node_handle`（C++17）允许安全提取/接合节点，理念源自 `list::splice`。\n",
    "  - `std::map::contains`（C++20）提供更简洁查找。\n",
    "- **C++20–23**\n",
    "  - `constexpr` 化核心成员；`extract` 支持 compile-time。\n",
    "  - Transparent comparator (`std::less<>`) 在 C++14 引入，用于异构查找。\n",
    "\n",
    "哈希容器 `unordered_*`\n",
    "\n",
    "- **C++11**：首次纳入标准，对应 SGI `hash_*`。\n",
    "- **C++14–17**：`reserve`, `rehash` 行为明确；`try_emplace`, `extract`, `merge`。\n",
    "- **C++20**：`contains`, `erase_if`。\n",
    "- **C++23**：`std::unordered_flat_map` 尚未标准化，但 P1222R6 已纳入 libstdc++ 扩展；`constexpr` 支持增强。\n",
    "- **新特性影响**：`std::hash` 支持更多类型；`std::pmr::unordered_map` 配合 polymorphic allocators。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 算法与仿函数篇\n",
    "\n",
    "基本算法\n",
    "\n",
    "- **SGI**：提供 `sort`, `merge`, `set_*`, `heap`, `find`, `for_each` 等实现。\n",
    "- **C++11**：算法与 `move`、`forward`、lambda 搭配，减少手写仿函数。\n",
    "- **C++14**：`std::equal`、`std::mismatch` 增加谓词默认模板参数。\n",
    "- **C++17**：\n",
    "  - **并行 STL 算法**：`std::for_each(std::execution::par, ...)`。\n",
    "  - `std::sample`, `std::clamp`, `std::reduce`, `std::transform_reduce`。\n",
    "  - `std::search` 支持 Boyer–Moore 搜索器。\n",
    "- **C++20**：\n",
    "  - **Ranges 算法**：`std::ranges::sort`, `std::ranges::copy`, `std::ranges::set_union` 等具 `range` + `iterator` + `sentinel` 接口。\n",
    "  - 投影（`proj`）参数，可直接使用 `&Type::member`。\n",
    "  - `constexpr` 算法范围扩大，可在编译期运行。\n",
    "- **C++23**：\n",
    "  - `std::ranges::to`, `ranges::chunk`, `ranges::slide`, `ranges::adjacent` 等高阶组合。\n",
    "  - `std::mdspan` 相关算法提案（P0009 集成）。\n",
    "\n",
    "仿函数与可调用对象\n",
    "\n",
    "- **SGI**：`unary_function`, `binary_function`, `bind1st`, `not1`。\n",
    "- **C++11**：lambda、`std::function`, `std::bind`、`std::mem_fn` 取代旧仿函数适配器。\n",
    "- **C++14**：泛型 lambda；`std::cref`, `std::ref` 泛化。\n",
    "- **C++17**：`std::invoke` 统一调用规则；`std::not_fn` 替代 `not1/2`；`std::apply`。\n",
    "- **C++20–23**：\n",
    "  - Concepts (`std::predicate`, `std::indirect_unary_predicate`) 约束可调用对象。\n",
    "  1. `std::bind_front`（C++20）替代部分 `std::bind` 用法。\n",
    "  2. `std::move_only_function`（C++23）为资源独占的泛型回调提供支持。\n",
    "\n",
    "适配器\n",
    "\n",
    "- **迭代器适配器**（SGI）：`insert_iterator`, `reverse_iterator`。\n",
    "- **Ranges 时代**：`std::views::reverse`, `std::views::filter`, `std::views::transform`, `std::views::iota`, `std::views::zip`（C++23）。\n",
    "- **容器适配器**：`std::stack`, `std::queue` 支持 `constexpr` 与 `emplace`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 字符串与扩展组件\n",
    "\n",
    "长字符串处理\n",
    "\n",
    "- **SGI**：`rope` 处理长字符串拼接。\n",
    "- **C++11–23**\n",
    "  - 标准未收录 rope；可关注 `std::pmr::string`, LLVM `llvm::rope`, Qt `QStringBuilder`.\n",
    "  - `std::string_view`（C++17）极大优化只读字符串操作；`std::format`（C++20）提供高性能格式化。\n",
    "  - C++23 `std::print` 直接输出，`std::expected` 改善错误处理链路。\n",
    "\n",
    "单向链表 `slist` → `forward_list`\n",
    "\n",
    "- `forward_list`（C++11）实质承袭 SGI `slist`。`splice_after`, `merge`, `remove_if` 在 C++20 后 `constexpr`。\n",
    "\n",
    "数值与辅助算法\n",
    "\n",
    "- `std::iota`, `std::accumulate`, `std::adjacent_difference` 进入 ranges；\n",
    "- C++20：`std::midpoint`, `std::lerp`, `std::ssize`、位操作（`std::popcount`）。\n",
    "- C++23：`std::roots`（多项式根求解 TS 讨论中），`std::lcm` `constexpr` 化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 现代特性补充：语言与库交互\n",
    "\n",
    "- **移动语义**（C++11）：\n",
    "  - 容器重新实现构造/赋值/插入逻辑；书中“先复制再销毁”模式需改写为“先移动再销毁”。\n",
    "  - `noexcept` 移动构造影响容器是否选择移动或复制。\n",
    "- **智能指针**（C++11）改变资源管理；`allocator` 结合 `shared_ptr` 搭配自定义删除器。\n",
    "- **异常安全**：`noexcept`、强异常保证在标准中被强化，现代容器 API 明确异常传播规则。\n",
    "- **多线程支持**（C++11 起）：标准库提供 `std::thread`, `std::mutex`, `std::condition_variable`；并行算法（C++17）结合容器使用需注意可重入性。\n",
    "- **`constexpr` 革命**（C++14–23）：\n",
    "  - C++23 几乎所有容器、算法在常量表达式中可用，促使编译期计算成为现实。\n",
    "- **模块与包**（C++20）：\n",
    "  - 标准库正在分步提供模块化接口（`std`, `std.compat`）。理解 SGI 配置头有助认识模块编译边界。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 学习建议（结合 C++11–23）\n",
    "\n",
    "1. **对照实现**\n",
    "\n",
    "   - 阅读 SGI 源码后，使用 GCC/Clang 的 libstdc++/libc++ C++23 版本源码进行对比，关注移动语义、`constexpr`、concepts 的落地。\n",
    "   - 利用 Compiler Explorer 同时查看 `-std=c++98` 与 `-std=c++20` 生成的容器实现差别。\n",
    "\n",
    "2. **逐步演练**\n",
    "\n",
    "   - 仿写简易 `vector`：在 SGI 风格基础上逐步加入 C++11 移动语义、C++17 `try_emplace`、C++20 concepts。\n",
    "   - 以 ranges 组合重构书中算法示例，例如：\n",
    "     ```cpp\n",
    "     auto result = text \n",
    "                 | std::views::split(' ')\n",
    "                 | std::views::transform([](auto word) { return std::string_view(word); })\n",
    "                 | std::ranges::to<std::vector>();\n",
    "     ```\n",
    "   - 练习 node handle：`auto node = map.extract(key); node.key() = newKey; otherMap.insert(std::move(node));`。\n",
    "\n",
    "3. **关注提案与文档**\n",
    "\n",
    "   - 阅读 Pxxxx 提案（尤其是 `ranges`, `flat_map`, `expected`, `mdspan`）理解设计理念。\n",
    "   - 查阅 `cppreference` “Since C++11/14/17/20/23” 区块，与书中旧接口互相印证。\n",
    "\n",
    "4. **选择性补课**\n",
    "\n",
    "   - 书中未覆盖的现代主题：`std::variant`、`std::expected`、协程 `std::generator`、`std::atomic_ref` 等，可通过 CppCon 演讲或 Modern C++ 书籍补充。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 总结\n",
    "\n",
    "- 侯捷《STL 源码剖析》在理解 STL 内核、内存池、红黑树、算法适配器方面仍具不可替代价值。\n",
    "- C++11–23 引入的移动语义、ranges、concepts、`constexpr`、并行执行策略等，要求我们把“SGI 实现”升级为“现代接口 + 旧原理”的混合视角。\n",
    "- 推荐在阅读书籍的同时，建立下面向现代标准的“对照表”：\n",
    "\n",
    "| 主题        | SGI 实现         | C++11                            | C++14          | C++17                   | C++20               | C++23                       |\n",
    "| ----------- | ---------------- | -------------------------------- | -------------- | ----------------------- | ------------------- | --------------------------- |\n",
    "| 容器搬运    | 拷贝             | Move, emplace                    | 泛型 lambda    | Node handle             | Ranges 约束         | `flat_map`, `constexpr`     |\n",
    "| 内存管理    | 双层配置器       | `allocator_traits`, `unique_ptr` | `make_unique`  | `pmr` TS                | `std::pmr` 正式     | `constexpr` allocator       |\n",
    "| 算法接口    | 迭代器 + 算法    | `std::move_iterator`             | 更丰富默认谓词 | 并行算法                | Ranges, projections | `ranges::to`, views         |\n",
    "| 仿函数      | `unary_function` | lambda, `std::function`          | 泛型 lambda    | `std::invoke`, `not_fn` | Concepts 约束       | `std::move_only_function`   |\n",
    "| 字符串/视图 | `rope`, `slist`  | `std::array`, `forward_list`     | -              | `std::string_view`      | `std::span`, ranges | `std::mdspan`, `std::print` |\n",
    "\n",
    "- 通过“传统源码推演 + 现代特性对照 + 实战练习”，能够构建跨时代的 C++ 标准库理解体系，既不忘根，又紧跟 C++23 前沿。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
